// 53. 最大子数组和
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int pre=0,maxAns=nums[0];
        for(const auto &x:nums){
            pre=max(pre+x,x);
            maxAns=max(maxAns,pre);
        }
        return maxAns;
    }
};

//56. 合并区间
class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        if(intervals.size()==0){
            return {};
        }
        sort(intervals.begin(),intervals.end());//按照区间的起始位置从小到大排序
        vector<vector<int>>merged;
        for(int i=0;i<intervals.size();i++){
            int L=intervals[i][0],R=intervals[i][1];

            if(!merged.size()||merged.back()[1]<L){//如果 merged 为空或者 merged 中最后一个区间的结束位置小于当前区间的起始位置，则将当前区间直接添加到 merged 中。         
                merged.push_back({L,R});//更新最大合并区间以及不能合并的区间
            }
            else{
                merged.back()[1]=max(merged.back()[1],R);//合并区间的过程

            }
        }
        return merged;
    }
};



//189. 轮转数组
class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n=nums.size();
        vector<int>newArr(n);
        for(int i=0;i<n;i++){
            newArr[(i+k)%n]=nums[i];
        }
        nums.assign(newArr.begin(),newArr.end());//它会替换掉容器中现有的所有元素。该方法接受两个迭代器作为参数，这两个迭代器定义了一个范围
    }
};

//238. 除自身以外数组的乘积
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n=nums.size();
        vector<int>L(n),R(n),answer(n);
        
         // 对于索引为 '0' 的元素，因为左侧没有元素，所以 L[0] = 1
        L[0]=1;
        for(int i=1;i<n;i++){
            // L[i] 为索引 i 左侧所有元素的乘积
            L[i]=L[i-1]*nums[i-1];
        }
        R[n-1]=1;
        for(int i=n-2;i>=0;i--){
            R[i]=R[i+1]*nums[i+1];
        }
        for(int i=0;i<n;i++){
            answer[i]=L[i]*R[i];
        }
        return answer;
    }
};

//41. 缺失的第一个正数
class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        int n=nums.size();
        int k=1;
        for(int i=0;i<n;i++){

             if(nums[i]&&nums[i]>k)
             break;
             else if(nums[i]&&nums[i]==k)
             k++;
        }
        return k;
    }
};